The primary ultrahigh energy particles which produce giant extensive air showers in the Earth atmosphere present an intriguing mystery from two points of view: (1) How are the base particles produced with such astounding energies, eight orders of magnitude higher than those produced by the best man-made terrestrial accelerators? (2) Since they are most likely extragalactic in origin, how do they reach us from extragalactic distances without suffering the severe losses expected from interactions with the 2.7 K thermal cosmic background photons, the so called GZK effect? The answers to these questions may involve new physics: violations of special relativity, grand unification theories, and quantum gravity theories involving large extra dimensions. They may involve new astrophysical sources, "zevatrons". Or some heretofore totally unknown physics or astrophysics may hold the answer. I will discuss here the mysteries involving the production and extragalactic propagation of ultrahigh energy cosmic rays and some suggested possible solutions.